// https://leetcode.cn/problems/max-consecutive-ones-iii/description/

// 算法思路总结：
// 1. 滑动窗口维护最多包含K个0的子数组
// 2. 统计窗口内0的个数作为收缩条件
// 3. 右指针扩展窗口，左指针在0超限时收缩
// 4. 实时更新最大有效窗口长度
// 5. 时间复杂度：O(n)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>

class Solution 
{
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        int n = nums.size(), Zeros = 0, ret = 0;

        for (int l = 0, r = 0 ; r < n ; r++)
        {
            if (!nums[r])
                Zeros++;
            while (Zeros > k)
            {
                if (!nums[l])
                    Zeros--;
                l++;
            }
            ret = max(ret, r - l + 1);
        }
        return ret;
    }
};

int main()
{
    vector<int> v1 = {1,1,1,0,0,0,1,1,1,1,0}, v2 = {0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1};
    int k1 = 2, k2 = 3;

    Solution sol;
    cout << sol.longestOnes(v1, k1) << endl;
    cout << sol.longestOnes(v2, k2) << endl;

    return 0;
}